﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0188_CanVisitAllRooms : IAlgorithm
    {
        // 841. 钥匙和房间

        // 有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。
        // 然而，你不能在没有获得钥匙的时候进入锁住的房间。
        // 当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。
        // 给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。


        // 提示：
        //  n == rooms.length
        //  2 <= n <= 1000
        //  0 <= rooms[i].length <= 1000
        //  1 <= sum(rooms[i].length) <= 3000
        //  0 <= rooms[i][j] < n
        //  所有 rooms[i] 的值 互不相同


        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
            //var res = Algorithm(param);
            //foreach (var item in res)
            //{
            //    foreach (var iitem in item)
            //    {
            //        Console.Write(iitem + " ");
            //    }
            //    Console.WriteLine();
            //}
        }

        // 算法
        public bool CanVisitAllRooms(IList<IList<int>> rooms)
        {
            var inMap = new HashSet<int>();
            var stack = new Stack<IList<int>>();
            stack.Push(rooms[0]);
            inMap.Add(0);
            while (stack.Count > 0)
            {
                var t = stack.Pop();
                foreach (var key in t)
                    if (!inMap.Contains(key))
                    {
                        inMap.Add(key);
                        stack.Push(rooms[key]);
                    }
            }
            return inMap.Count == rooms.Count;
        }
    }
}
